Vés al contingut

Teorema de flux màxim tall mínim

De la Viquipèdia, l'enciclopèdia lliure

En optimització i teoria de grafs, el teorema de flux màxim tall mínim postula que en una xarxa de flux, la quantitat màxima de flux que pot passar d'una font fins a un pou és igual a la capacitat mínima que necessitem treure-li a la xarxa perquè no pugui passar més flux de la font al pou.

El teorema de flux màxim tall mínim és un cas especial del teorema de dualitat i pot derivar-se en el teorema de Menger i el teorema de König-Egerváry.

Definició matemàtica

[modifica]

Sigui una xarxa (graf dirigit), i i la font i el pou d' respectivament.

La capacitat d'una aresta és c: ER+, denominada com cuv o c(u,v). Representa la quantitat màxima de flux que pot passar a través d'una aresta.
El flux és f: ER+, denominat com fuv o f(u,v), i subjecte a les següents dos restriccions:
  1. per cada (restricció de capacitat).
  2. per cada (conservació de flux).

El valor del flux és definit per | f | = Σv∈Vfsvv∈Vfvs, on s és la font de N. Representa la quantitat de flux que passa de la font al pou.

El problema de flux màxim pretén maximitzar |f|, és a dir, enviar tant de flux com sigui possible des de s fins t.

Un tall s-t és un tall en que s∈S i t∈T. El conjunt de tall de C és el conjunt {(u,v)∈E | u∈S, v∈T}. Si les arestes del conjunt de tall són eliminades, |f| = 0.

La capacitat d'un tall s-t és definida per c(S,T) = Σ(u,v)∈(S,T) cuv.

El problema del tall mínim pretén minimitzar c(S,T), és a dir, minimitzar la capacitat del tall s-t.

Postulat

[modifica]

El teorema de flux màxim tall mínim postula

El valor màxim d'un flux s-t és igual a la capacitat del tall s-t mínim.

Exemple

[modifica]
Xarxa amb els valor òptims

La figura de la dreta és una xarxa com a valor de flux 7. El vèrtex en blanc i els vèrtexs en gris pertanyen als subconjunts S i T d'un tall s-t, el conjunt de tall del qual conté les arestes discontínues. La capacitat del tall s-t és 7, com també el valor del flux. El teorema de flux màxim tall mínim ens diu que el valor del flux i la capacitat del tall s-t són ambdós òptims en aquesta xarxa.

Història

[modifica]

El teorema de flux màxim tall mínim va ser provat per P. Elias, A. Feinstein i C.E. Shannon el 1956, i independentment per L.R. Ford i D.R. Fulkerson el mateix any.

Vegeu també

[modifica]